package com.exercises;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

/**
 * 9x9 的数独是否有效
 */
public class Exercise456 {

    public static void main(String[] args) {
        System.out.println(new Exercise456().find132pattern(new int[]{1, 0, 1, -4, -3}));
    }

    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) return false;
        int minLeft = nums[0];
        TreeMap<Integer, Integer> rightAll = new TreeMap<Integer, Integer>();
        for (int i = 2; i < nums.length; i++) {
            rightAll.put(nums[i], rightAll.getOrDefault(nums[i], 0) + 1);
        }
        for (int j = 1; j < nums.length - 1; j++) {
            if (minLeft < nums[j]) {
                Integer next = rightAll.ceilingKey(minLeft + 1);
                if (next != null && nums[j] > next) {
                    return true;
                }
            }
            minLeft = Math.min(minLeft, nums[j]);
            int count = rightAll.get(nums[j + 1]);
            if (count - 1 == 0) {
                rightAll.remove(nums[j + 1]);
            } else {
                rightAll.put(nums[j + 1], count - 1);
            }
        }
        return false;
    }

}
